package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/8/12 0012.
 */

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */
public class 树的子结构 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;

        TreeNode subNode2 = new TreeNode(2);
        TreeNode subNode4 = new TreeNode(4);
        TreeNode subNode5 = new TreeNode(5);
        subNode2.left = subNode4;
        subNode2.right = subNode5;

        System.out.println(HasSubtree(node1, subNode2));
    }

    //找出值相等的节点，然后给isTheSameStructure函数做进一步的判断。
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val)
//                return isTheSameStructure(root1, root2);//这儿不能直接返回，因为如果为false，树应该向下遍历其他节点。
                // 因为有可能第一个找到的root1.val == root2.val的节点不满足子树结构条件，但是后续遍历中可能找到既满足root1.val == root2.val又满足子树结构的节点
                result= isTheSameStructure(root1, root2);
            if (!result)//result表示还未得到正确的结果，防止得到的结果都是root1.right与root2比较的结果。
                result = HasSubtree(root1.left, root2);
            if (!result)//result表示还未得到正确的结果
                result = HasSubtree(root1.right, root2);
        }
        return result;
    }

    //此函数的作用是找到了两个值相等的节点，遍历他们看是否结构相同且每个节点上的值也相同
    private static boolean isTheSameStructure(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 != null) return false;
        if (root2 == null) return true;
        if (root1.val != root2.val) return false;
        return isTheSameStructure(root1.left, root2.left) && isTheSameStructure(root1.right, root2.right);
    }

    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
